import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Random;
import java.util.Scanner;
import java.lang.Math;

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.MinPQ;
public class Board implements Comparable<Board>{
  int moves;
  int key;
  int[][] tiles;
    // create a board from an n-by-n array of tiles,
    // where tiles[row][col] = tile at (row, col)
    public Board(int[][] tiles)//这个的话就是预设在外面创建了一个数组然后传过来
    {
      //初始化数组
      this.tiles=tiles;
      // int n=tiles[0].length;
      // int n_sqare=n*n;
      // int number_tmp=0;
      // for(int i=0;i<n;i++)
      // {
      //   for(int j=0;j<n;j++)
      //   {
      //       tiles[i][j]=number_tmp;
      //       number_tmp++;
      //   }
      // }

      // //shuffle,随机洗牌，生成随机序列
      //  Sort sort=new Sort();
      // for(int i=1;i<n_sqare;i++)
      // {
      //   Random rand=new Random();
      //   int tmp=rand.nextInt(i+1);   //这里有一个二维到一维的拆分，直接多几个数传也行，但是比较麻烦。
      //   sort.Exchange(tiles,i,tmp);  //下次的话可以外面循环行和列，然后在循环内计算结果，然后再把结果传过去，避免错误和计算的麻烦，还有读着不方便
      // }
    }
                                           
    // string representation of this board
    //记住这个方法只能返回string
    public String toString()
    {
        int n=tiles.length;
        StringBuffer out=new StringBuffer();
        out.append(n);
        out.append("\n");
        for(int i=0;i<n;i++)
        {
          for(int j=0;j<n;j++)
          {
            out.append(tiles[i][j]);
            out.append(" ");
          }
          out.append("\n");
        }
        return out.toString();
    }

    // board dimension n
    public int dimension()
   {
      return tiles.length;
   }

 

    // number of tiles out of place
    //这个找的是，在错误位置的tile的个数，有一个加一个
    public int hamming()
    {
        int hammingDistance=0;
        for(int i=0;i<dimension();i++)
        {
          for(int j=0;j<dimension();j++)
          {
            if(tiles[i][j]==0)        //遇到空格的情况
            {
              continue;
            }
            if(j+i*dimension()+1!=tiles[i][j])
            {
              hammingDistance++;
            }
          }
        }
        return hammingDistance;
    }

    // sum of Manhattan distances between tiles and goal
    //这个找的是各个tile的Manhattan距离的和
    //而Manhattan距离指的是这个tile到他正确位置的距离（竖直距离与水平距离之和）
    //这里的正确位置，是指从第一个数开始应该是1，然后到最后一个n方减一，最后一个位置应该放零代表空白方格，也就是：
    //1 2             零到n方减一的顺序： 0 1
    //3 0                                2 3
    //这样
    public int manhattan()
    {
      int col,row,manhattan=0;
      for(int i=0;i<dimension();i++)
      {
        for(int j=0;j<dimension();j++)
        {
          if(tiles[i][j]==0)
          {
            continue;
          }
          col=(tiles[i][j]-1)%dimension();        //通过观察可以看到，如果是按照0到n方减一的顺序的话
          row=(tiles[i][j]-1)/dimension();        //可以按照Sort里的方法正确计算出行列（物理（也就是带零））
          manhattan+=Math.abs(i-row);             //而相比于那个顺序，现在顺序里每个数对应的位置，是上面顺序中，此数减一对应的数的位置
          manhattan+=Math.abs(j-col);             
        }
      }
      return manhattan;
    }

    // is this board the goal board?
    public boolean isGoal()
    {
      for(int i=0;i<dimension();i++)
      {
        for(int j=0;j<dimension();j++)
        {
          if(i==dimension()-1&&j==dimension()-1)
          {
            break;
          }
          if(tiles[i][j]!=i*dimension()+j+1)
          {
            return false;
          }
        }
      }
      return true;
    }

    // does this board equal y?
    public boolean equals(Object y)
    {
      if (y == null) {
        return false;
      }

      if (y.getClass() != this.getClass()) {
        return false;
      }
      final Board other=(Board)y;
      //先判断是否是相同维的
      if(this.dimension()!=other.dimension())
      {
         return false;
      }
      //然后判断每个位置的数是否相等
      for(int i=0;i<dimension();i++)
      {
        for(int j=0;j<dimension();j++)
        {
          if(tiles[i][j]!=other.tiles[i][j])
          {
            return false;
          }
        }
      }
      //如果相等，那么最终就到这了
      return true;
    }

    // all neighboring boards 返回相邻board的迭代器
    public Iterable<Board> neighbors()   //用一个list表示，然后返回迭代器
    {
       LinkedList<Board> neighbors=new LinkedList();
       int position_0_col=0;
       int position_0_row=0;
       //找到空白格的位置
       for(int i=0;i<dimension();i++)
       {
        for(int j=0;j<dimension();j++)
        {
          if(tiles[i][j]==0)
          {
            position_0_col=j;
            position_0_row=i;
            break;
          }
        }
       }
       //判断上下左右的不同情况，如果上下左右的格在正常范围内存在了，那么就可以将这个格与空白格交换的情况加入到list中
       //上
       if(position_0_row-1>=0)
       {
         int[][] tiles=new int[dimension()][dimension()];
         Board tmp=new Board(tiles);
      for(int i=0;i<dimension();i++)
      {
        for(int j=0;j<dimension();j++)
        {
          tmp.tiles[i][j]=this.tiles[i][j];
        }
      }
         int int_tmp=tmp.tiles[position_0_row-1][position_0_col];
         tmp.tiles[position_0_row-1][position_0_col]=0;
         tmp.tiles[position_0_row][position_0_col]=int_tmp;
         tmp.key=tmp.manhattan()+tmp.moves;
         neighbors.addLast(tmp);
       }
       //下
       if(position_0_row+1<dimension())
       {
         int[][] tiles=new int[dimension()][dimension()];
         Board tmp=new Board(tiles);
         for(int i=0;i<dimension();i++)
         {
           for(int j=0;j<dimension();j++)
           {
             tmp.tiles[i][j]=this.tiles[i][j];
           }
         }
         int int_tmp=tmp.tiles[position_0_row+1][position_0_col];
         tmp.tiles[position_0_row+1][position_0_col]=0;
         tmp.tiles[position_0_row][position_0_col]=int_tmp;
         tmp.key=tmp.manhattan()+tmp.moves;
         neighbors.addLast(tmp);
       }
       //左
       if(position_0_col-1>=0)
       {
         int[][] tiles=new int[dimension()][dimension()];
         Board tmp=new Board(tiles);
      for(int i=0;i<dimension();i++)
      {
        for(int j=0;j<dimension();j++)
        {
          tmp.tiles[i][j]=this.tiles[i][j];
        }
      }
      int int_tmp=tmp.tiles[position_0_row][position_0_col-1];
      tmp.tiles[position_0_row][position_0_col-1]=0;
      tmp.tiles[position_0_row][position_0_col]=int_tmp;
      tmp.key=tmp.manhattan()+tmp.moves;
      neighbors.addLast(tmp);
       }
       //右
       if(position_0_col+1<dimension())
       {
         int[][] tiles=new int[dimension()][dimension()];
         Board tmp=new Board(tiles);
      for(int i=0;i<dimension();i++)
      {
        for(int j=0;j<dimension();j++)
        {
          tmp.tiles[i][j]=this.tiles[i][j];
        }
      }
      int int_tmp=tmp.tiles[position_0_row][position_0_col+1];
      tmp.tiles[position_0_row][position_0_col+1]=0;
      tmp.tiles[position_0_row][position_0_col]=int_tmp;
      tmp.key=tmp.manhattan()+tmp.moves;
      neighbors.addLast(tmp);
       }
       return neighbors;
    }

    // a board that is obtained by exchanging any pair of tiles
    //交换任意一对非空白的tile，用于A*搜索算法的启发式搜索算法
    //这里就交换前两个非空白tile
    public Board twin()
    {
        int n=dimension();
        int[][] a=new int[n][n];
        Board reBoard=new Board(a);
        for(int i=0;i<n;i++)
        {
          for(int j=0;j<n;j++)
          {
            reBoard.tiles[i][j]=tiles[i][j];
          }
        }
        int cir_judge_enough=0,exchange1=0,exchange2=0;
          for(int i=0;i<n;i++)
          {
            for(int j=0;j<n;j++)
            {
              if(tiles[i][j]!=0)
              {
                cir_judge_enough++;
                if(cir_judge_enough==1)
                {
                  exchange1=i*n+j;
                  continue;
                }
                if(cir_judge_enough==2)
                {
                  exchange2=i*n+j;
                  break;
                }
              }
            }
          }
        Sort sort=new Sort();
        sort.Exchange(reBoard.tiles, exchange1, exchange2);
        return reBoard;
    }

    //这里实现一个比较器用来给优先队列使用
    //实现完感觉这个好像没什么用，这个是用来给，以一个为标准，然后另外两个相对大小的
    public Comparator<Board> manhattanOrder()
    {
      return new Comparator<Board>() {
        public int compare(Board a,Board b)
        { 
           if(a.key==b.key)
           {
            return 0;
           }
           else if(a.key>b.key)
           {
            return 1;
           }
           else
           {
            return -1;
           }   
        }
      };
    }
   

    //那么这里实现以下compareTo
    //这里的两个比较都先用的Manhattan距离
    public int compareTo(Board b)
    {
      if(this.manhattan()>b.manhattan())
      {
        return 1;
      }
      else if(this.manhattan()==b.manhattan())
      {
        return 0;
      }
      else
      {
        return -1;
      }
    }

    // unit testing (not graded)
    public static void main(String[] args)
    {
         // create initial board from file
        Scanner scanner=new Scanner(System.in);
         int n = scanner.nextInt(); 
         int[][] tiles = new int[n][n];
         Board initial = new Board(tiles);
        for (int i = 0; i < n; i++)
         for (int j = 0; j < n; j++)
            initial.tiles[i][j] = scanner.nextInt();

          System.out.printf(initial.toString());
          Board twin=initial.twin();
          System.out.printf(twin.toString());
          MinPQ test=new MinPQ<Board>(initial.manhattanOrder());
          int init=initial.manhattan();
          int twinInt=twin.manhattan();
          test.insert(initial);
          test.insert(twin);

         int a=1;
    }
}
